import collections
class Solution(object):
    def findRotateSteps(self, ring, key):
        """
        :type ring: str
        :type key: str
        :rtype: int
        """
        m = len(ring)
        r = collections.defaultdict(set)
        for id, c in enumerate(ring):
            r[c].add(id)
        n = len(key)
        DP = []
        for c in key:
            d = {}
            for t in r[c]:
                d[t] = - 1
            DP.append(d)
        base = n
        for c in DP[0]:
            DP[0][c] = min(c, m - c)
        for i in range(1, n):
            for c2 in DP[i]:
                for c1 in DP[i - 1]:
                    if DP[i][c2] == -1:
                        DP[i][c2] = DP[i - 1][c1] + min(abs(c2 - c1), m - abs(c2 - c1))
                    else:
                        DP[i][c2] = min(DP[i - 1][c1] + min(abs(c2 - c1), m - abs(c2 - c1)), DP[i][c2])
        min_value = float('inf')
        for c in DP[-1]:
            min_value = min(min_value, DP[-1][c])
        return min_value + base





data = Solution()
ring = "godding"
key = "gd"
print(data.findRotateSteps(ring, key))
